package Solution.problem043;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description: 他这个的好处是转化成int的次数少，用List<Integer> 存储，减少了转换次数。
 * @author: lishangsheng
 * @create: 2019/03/29 11:36
 */


public class BetterSolution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0 || num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        char[] c1 = num1.toCharArray();
        char[] c2 = num2.toCharArray();

        List<Integer> res = new ArrayList<Integer>();

        for (int i = 0; i < c2.length; ++i) {
            List<Integer> prod = digitMultiplyStr(c1, c2, i);
            res = add2Lsts(res, prod);
        }

        // res -> string
        StringBuilder sb = new StringBuilder();
        for (int i = res.size() - 1; i >= 0; --i) {
            sb.append(res.get(i));
        }

        return sb.toString();

    }

    private List<Integer> digitMultiplyStr(char[] c1, char[] c2, int idx) {
        // i -> digit = c2[i]
        List<Integer> lst =new ArrayList<Integer>();
        int digit = c2[idx] - '0';
        if (digit == 0) {
            lst.add(0);
            return lst;
        }

        for (int i = 0; i < c2.length - idx - 1; ++i) {
            lst.add(0);
        }

        int carry = 0;
        for (int i = c1.length - 1; i >= 0; --i) {
            int prod = (c1[i] - '0') * digit + carry;
            carry = prod / 10;
            prod %= 10;
            lst.add(prod);
        }

        if (carry != 0) {
            lst.add(carry);
        }

        // reverse order product
        return lst;
    }

    private List<Integer> add2Lsts(List<Integer> l1, List<Integer> l2) {
        if (l1 == null || l1.size() == 0) {
            return l2;
        }

        if (l2 == null || l2.size() == 0) {
            return l1;
        }

        int i = 0, j = 0;
        int carry = 0;
        List<Integer> lst = new ArrayList<Integer>();
        while (i < l1.size() || j < l2.size() || carry != 0) {
            int n1 = 0, n2 = 0;
            if (i < l1.size()) {
                n1 = l1.get(i++);
            }
            if (j < l2.size()) {
                n2 = l2.get(j++);
            }

            int sum = n1 + n2 + carry;
            carry = sum / 10;
            sum %= 10;
            lst.add(sum);
        }

        return lst;
    }
}
